""" hash表
分治算法
排序
随机化
投票
 """
# hash table
 
from typing import List
def majorityElement(nums: List[int]) -> int:
    key = set(nums)
    dummy = [0]*len(key)
    dic = dict(zip(key, dummy))
    for i in nums:
        dic[i] = dic[i]+1


    for num in dic:
        if dic[num] > (len(nums)/2):
            return num

# vote algorithm

        can = 0
        num = 0 
        for i in nums:
            if num == 0:
                can = i
            if can == i:    
                num += 1
            else:
                num -= 1
            
        return can

print(majorityElement([3,2,3]))
